package main

import (
	"bytes"
	"fmt"
	"sort"
)

func frequencySort2(s string) string {
	m := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		_, ok := m[s[i]]
		if ok {
			m[s[i]]++
		} else {
			m[s[i]] = 1
		}
	}

	for k, v := range m {
		fmt.Println(string(k), ":", v)

	}

	type pair struct {
		k   byte
		cnt int
	}

	data := make([]pair, 0)

	for b, cnt := range m {
		p := pair{
			k:   b,
			cnt: cnt,
		}
		data = append(data, p)
	}
	sort.Slice(data, func(i, j int) bool {
		if data[i].cnt > data[j].cnt {
			return true
		}

		return false
	})

	res := make([]byte, 0)

	for i := 0; i < len(data); i++ {
		res = append(res, bytes.Repeat([]byte{data[i].k}, data[i].cnt)...)
	}

	return string(res)
}
func frequencySort(s string) string {
	cnt := map[byte]int{}
	for i := range s {
		cnt[s[i]]++
	}

	type pair struct {
		ch  byte
		cnt int
	}
	pairs := make([]pair, 0, len(cnt))
	for k, v := range cnt {
		fmt.Println(string(k), ":", v)
		pairs = append(pairs, pair{k, v})
	}
	sort.Slice(pairs, func(i, j int) bool { return pairs[i].cnt > pairs[j].cnt })

	ans := make([]byte, 0, len(s))
	for _, p := range pairs {
		ans = append(ans, bytes.Repeat([]byte{p.ch}, p.cnt)...)
	}
	return string(ans)
}
